1. Technical Field
The present invention relates in general to a system and method for compacting computer system heaps. More particularly, the present invention relates to a system and method for improving heap compaction during a garbage collection cycle in an environment such as that used in a Java virtual machine.
2. Description of the Related Art
Middleware environments, such as that provided by a Java virtual machine (JVM), often use a heap to store objects created in the environment. The Java virtual machine's heap stores all objects created by a running Java application. Objects are created by various instructions (e.g., the new, newarray, anewarray, multianewarray instructions), but are never freed (i.e., released) explicitly by the code. Garbage collection is the process of automatically freeing objects that are no longer referenced by the program.
The Java virtual machine specification does not require any particular garbage collection technique. The name “garbage collection” implies that objects no longer needed by the program are “garbage” and can be thrown away. A more accurate and up-to-date metaphor might be “memory recycling.” When an object is no longer referenced by the program, the heap space it occupies can be recycled so that the space is made available for subsequent new objects. The garbage collector must somehow determine which objects are no longer referenced by the program and make available the heap space occupied by such unreferenced objects.
In addition to freeing unreferenced objects, a garbage collector may also combat heap fragmentation. Heap fragmentation occurs through the course of normal program execution. New objects are allocated, and unreferenced objects are freed such that free portions of heap memory are left in between portions occupied by live objects. Requests to allocate new objects may have to be filled by extending the size of the heap even though there is enough total unused space in the existing heap. This will occur if there is not enough contiguous free heap space available into which the new object will fit. On a virtual memory system, the extra paging (or swapping) required to service an ever growing heap can degrade the performance of the executing program. On an embedded system with low memory, fragmentation could cause the virtual machine to “run out of memory” unnecessarily. In addition, most virtual machines have a limit on the size of the heap. In these systems, fragmentation may cause an application to stop running even though there is enough total free space in the heap.
Garbage collection performs the burden of freeing allocated memory. Determining when to explicitly free allocated memory can be difficult. Delegating this task to the Java virtual machine has several advantages. First, it can increase programmer productivity. When programming in non-garbage-collected languages a programmer can spend extensive amounts of time detecting and fixing an elusive memory problem.
A second advantage of garbage collection is that it helps ensure program integrity. Garbage collection is an important part of Java's security strategy. Java programmers are unable to accidentally (or purposely) crash the Java virtual machine by incorrectly freeing memory.
A challenge of a garbage-collected heap is that it adds an overhead that can affect program performance. The Java virtual machine has to keep track of which objects are being referenced by the executing program, and finalize and free unreferenced objects on the fly. This activity likely requires more CPU time than would be needed if the program explicitly freed unnecessary memory. In addition, programmers in a garbage-collected environment have less control over the scheduling of CPU time devoted to freeing objects that are no longer needed.
An additional challenge of a garbage-collected heap is that it periodically needs to be compacted in order to combat heap fragmentation. During compaction, objects are moved in order to defragment the heap space. Defragmenting the heap space results in objects being moved to a contiguous memory region with little or no memory between the moved objects. The movement of objects results in larger contiguous blocks of free space that can be used to store additional (i.e., new) objects. During compaction of a traditional garbage-collected heap, the entire heap is traversed and many objects are moved within the heap. Heap sizes can be quite large and can store hundreds or thousands of objects. Consequently, moving such a large amount of objects takes considerable computing resources. The use of the resources to perform compaction often causes a noticeable pauses to the user, as well as software applications, using the computer.
What is needed, therefore, is a system and method that incrementally compacts the heap so that a portion, or region, of the heap is compacted rather than compacting the entire heap. In addition, what is needed is a system and method that utilizes multiple processors to divide the region being compacted into multiple sections with each section being compacted by a separate processing thread. Furthermore, what is needed is a system and method that is able to work in an environment where some objects in the heap cannot be moved.